动态规划 - Dynamic Programming

Posted on | Edited on | In | Comments:

Those who cannot remember the past are condemned to repeat.

-Dynamic Programming

今天的算法课讲的就是动态规划，虽早已久仰大名，但始终不太懂背后原理。听完课后赶紧把今天学到的东西记下来。

动态规划和分治法有类似之处，他们都是通过组合子问题的解来求解原问题。不同之处在于，分治法常常用于将原问题划分为几个互不相交的子问题，如果划分后，有很多完全相同的子问题，那就使用动态规划的思路比较好。例如快速排序，将一段数组以枢纽值为界一分为二，再将这两段分别排序。将分出来的两段数组分别排序就是互不相交的两个子问题，可以使用分治法来解决。再如求斐波那契数列的第n项问题，我们知道斐波那契数列的规律是
$$
F(0) = 0 \quad F(1) = 1 \quad F(n) = F(n - 1) + F(n - 2) (n >= 2)
$$
我们发现求F(n)需要计算F(n-1)和F(n-2)，可是当计算F(n-1)和F(n-2)时，都需要计算F(n-3)，这样就造成了重复计算，大幅降低了效率，而动态规划算法的目的就是避免此类重复计算。

去年暑假，我好好思考了一下上台阶问题：

有100级台阶，每次只允许上1级台阶或上2级台阶，若要求上完全部台阶，共有多少种上法？

第一次看到还以为是组合数学问题，后来也没做出来。再一想，要不直接枚举吧，那这样的数据规模是惊人的，是指数级的时间复杂度。

emmm~我们考虑一下分治法吧。假设一下，现在已经站在了第100层台阶上，回忆一下刚刚最后一步我是怎么上来着的。我最后一步可以是从98层一步跨上来的，也可以是从99层踩上一级台阶上来。这时让我们时光倒流，我们可以选择最后一步从98层跨两级上来，也可以选择从99层爬一级上来。

现在我们将这两种可能分开讨论，如果我限定最后一步只能走一步，那么之前我就必须上到99层，而99层到100层只有1条路可走，上到100层的上法就等于上到99层的上法，所以我现在只要得知上到99层有多少种上法，就知道了上到100层有多少种上法；同理，如果我限定最后一步必须跨两步，那么我之前就必须上到98层，所以我现在只要得知上到98层有多少种上法，98层到100层也只有跨两级这一条路，所以上到100层的上法就等于上到98层的上法了。

现实里，最后一步可以跨两级，也可以只爬一级，所以上到100层的上法，应该等于上到98层的上法加上上到99层的上法。如果用函数F(n)表示上到第n层一共有多少种上法，那么就有F(100) = F(99) + F(98)，接下来也有F(99) = F(98) + F(97)，F(98) = F(97) + F(96)……。

这样问题就很简单了，只要这样不断递归下去，总会递归到一个终点，这个终点就是F(1)和F(2)，上一层台阶有多少种上法呢，显然除了一步跨上去没别的方法了吧，所以F(1) = 1；上两层台阶呢？一步一步爬，或是一步跨两个，F(2)应该等于2。那么现在的递归式应该是：
$$
F(1) = 1 \quad F(2) = 2 \quad F(n) = F(n - 1) + F(n - 2) (n > 2)
$$
将n取值为100，这样我们就可以算出结果了，用c++写出的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
using namespace std;

long F(int n) {
    if (n == 1) {
        return 1;
    } else if (n == 2) {
        return 2;
    } else {
        return F(n - 1) + F(n - 2);
    }
}

int main() {
    long result = F(100);
    cout << result;
    return 0;
}

这个代码跑很久都是跑不出来的，就是因为重复计算的部分太多了，详细讲来，如果我们要算f(100)，那么我们需要先得知f(99)和f(98)，然后想要得知f(99)和f(98)，都需要先算出f(97)，这样f(97)就计算了两遍，造成了重复计算，浪费了大量时间。上面代码中包含大量重复计算的内容，而动态规划算法就很好的解决了重复计算的问题。

现在我们不再从100层开始逐层向下递归，而是从第一层开始逐层向上走。什么意思呢？正如上面提到的问题，如果从下往上计算的话，我们先算出了f(97)的值，然后在计算f(99)和f(98)的时候，就可以共享一个计算成果，不需要花两倍的时间来计算。

从底层开始计算时，我们首先得知f(1) = 1以及f(2) = 2，根据F(n) = F(n - 1) + F(n - 2)的公式，可以很轻松算出F(3) = 3，F(4) = 5，然后继续向下推，直到n到100就可以得到结果。用代码实现的话，可以新开一个数组array，array[n]内存储了F(n)的结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <vector>
using namespace std;

long F(int n) {
    vector<long> array(n + 1, 0);
    array[1] = 1;
    array[2] = 2;
    
    for (int i = 3; i <= n; i++)
        array[i] = array[i - 1] + array[i - 2];

    return array[n];
}

int main() {
    long result = F(100);
    cout << result;
    return 0;
}

这里只需要一个循环就可以得出结果啦~这个代码的时间复杂度是O(n)，但是我们的空间复杂度也达到了O(n)，我们发现很多数据都是只使用了一次就不再使用了，将这个数组改为3个变量循环交替使用可以加大使用效率。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <vector>
using namespace std;

long F(int n) {
    long A, B, C;
    A = 1;
    B = 2;
    
    if (n == 1) return A;
    else if (n == 2) return B;
    else {
        for (int i = 3; i <= n; i++) {
            C = A + B;
            A = B;
            B = C;
        }
        return C;
    }
}

int main() {
    long result = F(100);
    cout << result;
    return 0;
}

我们使用3个变量ABC交替使用，只要始终保持ABC的先后顺序就可以啦！这种方法还将空间复杂度降为了O(1)。当然这题我们发现刚好是求斐波那契数列的第101项，如果我们直接使用斐波那契数列求第n项公式可以在常数级的时间内求出结果，但那和动态规划没有关系啦~

总结一下：线性规划就是先用分治法的方法，从终点往前思考，用递归的方式定义解；然后我们发现其中有很多重复的子问题，这样我们又从起点开始，逐步记录已经求好的子问题的解，然后需要时再拿出来用，以此节约时间。